package com.zwj.interview.链表;

/**
 * 如果给定一个链表，请问如何删除链表中的倒数第k个节点？假设链表中节点的总数为n，那么1≤k≤n。要求只能遍历链表一次
 * 关键在于两个指针的移动
 *
 * LC19
 */
public class 删除单链表倒数第K个节点 {

    /**
     * 整体的逻辑就是：让快节点先走K步，然后快慢节点同时走，快节点走完时，那么慢节点就来到了要删除的节点的前一个节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast=dummy;
        ListNode slow=dummy;
        //fast先走 k 步
        for(int i=0;i<n;i++){
           fast=fast.next;
        }
        while(fast.next!=null){
           slow=slow.next;
           fast=fast.next;
        }
        //删除第K个节点
        slow.next=slow.next.next;
        return dummy.next;
    }








}
